/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package grafrajz.utils;

import java.awt.Color;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
 *
 * @author adam_fejes_dell
 * A programban használt speciális gráfalgoritmusokat tartalmazó osztály
 */
public class Algorithms {
    
    private Map<Node, Color> color = new HashMap<Node, Color>();
    private Map<Node, Node> parent = new HashMap<Node, Node>();
    private Map<Node, Integer> inCount = new HashMap<Node, Integer>();
    private Map<Node, Integer> outCount = new HashMap<Node, Integer>();
    private int in, out;
    private Graph graph;
    
    /**
     * Megállapítja a gráfról, hogy tartalmaz-e kört
     * @param graph
     * @param e
     * @return 
     * NEM MŰKÖDIK
     */
    public boolean noCircle(Graph graph, Edge e){
        this.graph = graph;
        
        melysegiBejaras(graph);
        
        ArrayList<Edge> edges = graph.getAllEdges();
        edges.add(e);
        
        for(Edge edge : edges){
            //Vissza él || Előre él || kereszt él
            if(inCount.get(edge.getSource()) > inCount.get(edge.getDest()) || 
            inCount.get(edge.getSource()) + 1 < inCount.get(edge.getDest()) ||
            parent.get(e.getSource()) != e.getDest() || parent.get(e.getDest()) != e.getSource()){
                
                //graph.removeEdge(e);
                //System.out.println("Kör van benne ez nem fog menni");
                return false;
            }
                
        }
        
        //System.out.println("Nincs benne kör, oké!");
        return true; 
    }
    
    /**
     * Véggrehajt a gráfon egy Mélységi bejárást és a kapott fa éleit pirosra színezi
     * @param g 
     */
    public void melysegiBejaras(Graph g){
        ArrayList<Node> nodes = g.getAllNodes();
        
        for(Node n : nodes){
            color.put(n, Color.white);
            parent.put(n, null);
            inCount.put(n, 0);
            outCount.put(n, 0);
            
            //System.out.println("Csúcs és él száma: " + n + n.getEdgeCount());
        }
        
        in = 0;
        out = 0;
        
        for(Node n : nodes){
            //System.out.println("MB hívás előtt Csúcs és él száma: " + n + n.getEdgeCount());
            if(color.get(n) == Color.white)
                MB(n, g);
        }
        
        
        ArrayList<Edge> edges = g.getAllEdges();
        
        for(Edge edge : edges){
            if(g.isDirected()){
                if(parent.get(edge.getDest()).getName().equals(edge.getSource().getName()))
                    edge.setColor(Color.red);
            }
            else{
                
                ////System.out.println("Parent vizsgálat: " + edge);
                ////System.out.println("parent getDest: " + parent.get(edge.getDest()));
                ////System.out.println("parent getSource: " + parent.get(edge.getSource()));
                if((parent.get(edge.getDest()) != null && (parent.get(edge.getDest()).getName().equals(edge.getSource().getName()))) || (parent.get(edge.getSource()) != null  && parent.get(edge.getSource()).getName().equals(edge.getDest().getName())))
                    edge.setColor(Color.red);
               else if(parent.get(edge.getDest()) == null || parent.get(edge.getSource()) == null)
                    edge.setColor(Color.red);
            }
        }
    }
    
    /**
     * Mélységi bejárás rekurzív metódusa
     * @param n
     * @param graph 
     */
    private void MB(Node n, Graph graph){
        //System.out.println("MB ezen a gráfon fut: " + graph);
        //System.out.println("MB fut ezen a csúcson: " + n);
        color.put(n, Color.gray);
        in++;
        inCount.put(n, in);
        
        //System.out.println("MBben Csúcs és él száma: " + n + n.getEdgeCount());
        
        ArrayList<Node> neighbours = graph.getNeighbours(n);
        //System.out.println("szomszéd szám: " + neighbours.size());
        for(Node neighbour : neighbours){
            //System.out.println("szomszéd szaromat nyomdszét: " + neighbour );
            if(color.get(neighbour) == Color.white){
                //System.out.println(neighbour + " szülője lesz: " + n );
                parent.put(neighbour, n);
                //System.out.println("Kezdődik a rekurzió");
                //System.out.println("MB rekurzív hívás előtt Csúcs és él száma: " + neighbour + neighbour.getEdgeCount());
                MB(neighbour, graph);
            }
            color.put(n, Color.black);
            out++;
            outCount.put(n, out);              
        }
        
    }
}
